Graphic images displayed on computer screens are most often stored in the memory of the computer as a list of graphics objects. This list includes the color of the graphics object, the location for displaying the graphics object on the screen, and other information. When displaying the graphic image, this list is processed, called traversing, and each graphics object is selected from the list and displayed, or rendered, on the graphic screen at the location defined in the list. Thus, the entire graphic image exists only on the screen. When a new graphics object, for example a line, is placed in the image on the screen, a new list element is created for the line indicating the starting and end points of the line, and a new screen image is displayed from the list.
One of the operations that is commonly done by a user to a graphics image is to select one of the graphics objects and perform some operation on the selected graphics object. For example, the color of the selected graphics object could be changed, the graphics object could be deleted, etc. To the user of the system, a graphics object is selected by using a pointer device, such as a mouse, moving the screen pointer to the graphics object by moving the pointer device, and selecting the graphics object by clicking the pointer device button. The graphics object is then highlighted on the screen, either by intensifying the graphics object or changing the color of the graphics object, to indicate to the user which graphics object has been selected. After the selection, the user then performs the operation on the graphics object using either the mouse or the keyboard as input.
To perform the selection, or picking, operation, prior art systems traverse the entire list of graphics objects whenever the selection button on the mouse is pressed. As each graphics object is rendered during this traversal, i.e. the graphics object is constructed to be placed on the screen, the location of the pointer on the screen is compared to the location of each pixel of the graphics object, and if a match occurs, the graphics object is considered to be selected. This method is slow, however, since every graphics object up to the selected graphics object must be rendered even though only the last one is being selected. Thus, prior art methods have a performance proportional to the number of graphics objects in the display list and their performance is roughly equal to the time to display the entire graphics image or scene.
The IBM model 5080 system continually refreshes the screen from the display list, thus this system can pick during the refresh cycle using special hardware. When displaying large numbers of graphics primitives, however, flicker occurs in this system.
One prior art solution for this problem is discussed in Computer Graphics Principles and Practice, by Foley et al., Addison Wesley, 1990, pp. 48-50. This method divides the screen area into regions so that only the graphics objects contained within the region need be rendered in order to determine whether one of the graphics objects has been picked.
The concept of item buffers and picking is disclosed in "Direct WYSIWYG Painting and Texturing on 3D Shapes" Hanrahan et al., Computer Graphics, Volume 24, number 4, August 1990, p. 218. This article discloses the general concept of item buffers, but provides no detail on how to implement an item buffer.
There is a need in the art then to improve performance in the method of picking a graphics object on a graphics screen. There is a further need to pick the graphics object without having to traverse the entire graphics objects list. The present invention meets these and other needs.